package org.apache.commons.graph.algorithms.visit

import org.apache.commons.graph.DirectedGraph
import org.apache.commons.graph.Graph
import org.apache.commons.graph.algorithms.visit.internal.VisitGraphBuilder
import org.apache.commons.graph.bean.VertexPair

/*
* Licensed to the Apache Software Foundation (ASF) under one
* or more contributor license agreements.  See the NOTICE file
* distributed with this work for additional information
* regarding copyright ownership.  The ASF licenses this file
* to you under the Apache License, Version 2.0 (the
* "License"); you may not use this file except in compliance
* with the License.  You may obtain a copy of the License at
*
*   http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing,
* software distributed under the License is distributed on an
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
* KIND, either express or implied.  See the License for the
* specific language governing permissions and limitations
* under the License.
*/

/**
 * Applies different implementations of Graph visitor algorithms.
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
 * @param <G> the Graph type
</G></E></V> */
interface VisitAlgorithmsSelector<V, E, G : Graph<V, E>> {
    /**
     * Breadth-first search algorithm implementation.
     *
     * @return the breadth first search tree
     */
    fun applyingBreadthFirstSearch(): Graph<V, E>?

    /**
     * Breadth-first search algorithm implementation.
     *
     * @param handler the handler intercepts visit actions
     */
    fun <O> applyingBreadthFirstSearch(handler: GraphVisitHandler<V, E, G, O>): O?

    /**
     * Depth-first search algorithm implementation.
     *
     * @return the depth first search tree
     */
    fun applyingDepthFirstSearch(): Graph<V, E>?

    /**
     * Depth-first search algorithm implementation.
     *
     * @param handler the handler intercepts visit actions
     */
    fun <O> applyingDepthFirstSearch(handler: GraphVisitHandler<V, E, G, O>): O?
}


/**
 * [VisitAlgorithmsSelector] implementation.
 *
 * @param <V> the Graph vertices type
 * @param <E> the Graph edges type
 * @param <G> the Graph type
</G></E></V> */
internal class DefaultVisitAlgorithmsSelector<V, E, G : Graph<V, E>>(
    /** The graph.  */
    private val graph: G,
    /** The start vertex for the search.  */
    private val source: V
) : VisitAlgorithmsSelector<V, E, G> {
    /**
     * {@inheritDoc}
     */
    override fun applyingBreadthFirstSearch(): Graph<V, E>? {
        return applyingBreadthFirstSearch(VisitGraphBuilder())
    }

    /**
     * {@inheritDoc}
     */
    override fun <O> applyingBreadthFirstSearch(handler: GraphVisitHandler<V, E, G, O>): O? {
        return applyingSearch(handler, true)
    }

    /**
     * {@inheritDoc}
     */
    override fun applyingDepthFirstSearch(): Graph<V, E>? {
        return applyingDepthFirstSearch(VisitGraphBuilder())
    }

    /**
     * {@inheritDoc}
     */
    override fun <O> applyingDepthFirstSearch(handler: GraphVisitHandler<V, E, G, O>): O? {
        return applyingSearch(handler, false)
    }

    /**
     * A generalized graph search algorithm to be used to implement depth-first and breadth-first searches. Depending on
     * the used collection, the algorithm traverses the graph in a different way:
     *
     *  * Queue (FIFO): breadth-first
     *  * Stack (LIFO): depth-first
     *
     *
     * @param handler the handler intercepts visits
     * @param enqueue defines the collection behavior used to traverse the graph: true is a Queue, false is a Stack
     * @return the result of [GraphVisitHandler.onCompleted]
     */
    private fun <O> applyingSearch(handler: GraphVisitHandler<V, E, G, O>, enqueue: Boolean): O? {
        //var handler = handler
        //handler = Assertions.checkNotNull(handler, "Graph visitor handler can not be null.")

        handler.discoverGraph(graph)

        val vertexList = mutableListOf<VertexPair<V>>()

        vertexList.add(VertexPair(source, source))

        val visitedVertices: MutableSet<V> = HashSet()
        visitedVertices.add(source)

        var visitingGraph = true

        while (visitingGraph && vertexList.isNotEmpty()) {
            // if dequeue, remove the first element, otherwise the last
            val pair = if (enqueue) vertexList.removeFirst() else vertexList.removeLast()
            val v = pair.head
            val prevHead = pair.tail
            val e = if (prevHead == v) null else graph.getEdge(prevHead, v)

            var skipVertex = false

            if (e != null) {
                // if the vertex was already visited, do not discover
                // another edge leading to the same vertex
                if (visitedVertices.contains(v)) {
                    skipVertex = true
                } else {
                    val stateAfterEdgeDiscovery = handler.discoverEdge(prevHead, e, v)
                    if (VisitState.CONTINUE != stateAfterEdgeDiscovery) {
                        skipVertex = true
                        if (VisitState.ABORT == stateAfterEdgeDiscovery) {
                            visitingGraph = false
                        }
                    }

                    if (VisitState.ABORT == handler.finishEdge(prevHead, e, v)) {
                        skipVertex = true
                        visitingGraph = false
                    }
                }
            }

            // only mark the current vertex as visited, if the
            // edge leading to it should be expanded
            var vertexWasDiscovered = false
            if (!skipVertex) {
                visitedVertices.add(v)
                val stateAfterVertexDiscovery = handler.discoverVertex(v)
                vertexWasDiscovered = true
                if (VisitState.CONTINUE != stateAfterVertexDiscovery) {
                    skipVertex = true
                    if (VisitState.ABORT == stateAfterVertexDiscovery) {
                        visitingGraph = false
                    }
                }
            }

            if (!skipVertex) {
                val connected =
                    if (graph is DirectedGraph<*, *>)
                        (graph as DirectedGraph<V, E>).getOutbound(v).iterator()
                    else
                        graph.getConnectedVertices(v).iterator()

                while (connected.hasNext()) {
                    val w = connected.next()
                    if (!visitedVertices.contains(w)) {
                        vertexList.add(VertexPair(w, v))
                    }
                }
            }

            if (vertexWasDiscovered && VisitState.ABORT == handler.finishVertex(v)) {
                visitingGraph = false
            }
        }

        handler.finishGraph(graph)

        return handler.onCompleted()
    }
}
